神仙题,抢个第一篇题解
题目大意:一条链上有 个点,有 条连接两个点的管道,所有管道必须钻一遍,求s到其他点的最短路
定义一条路径中,不走管道的那部分路径叫做自由路径。由于所有管道的长度和是固定的,那么我们要求的就是让自由路径长度最少
如果没有管道,路径肯定是从 到 的一条自由路径。假设现在有一条自由路径从 到 (),有一条管道从 到 (),考虑以下几种情况:
-
,我们可以把路径变成,最终的自由路径变成 到 和 到 。的情况同理。
-
,还是把路径变成,最终的自由路径还是 到 和 到
-
,直接在 上加一条自由路径让它变成一个环(这里先不考虑图的连通性问题,一个环暂时可以认为是独立于其他部分存在的。连通性会在后面处理)
注意:因为是无向边,而且一条路径也可以翻转,所以方向并不重要
根据上面几种情况找规律,发现在原有的自由路径上加一条管道,相当于把管道那段区间反转。当然这只是找规律,实际上这样做是正确的,下面是证明:
可以发现每次添加管道并反转自由路径后,所有管道边和自由边维持了一个从 到 的欧拉路,因此这条路径一定可行。同时它一定是最短的,因为所有的自由边都没有交叉。
只不过剩下一个很严重的问题:上面所说的“欧拉路”不是真正意义上的欧拉路,因为这些路径可能还没连通呢,只是满足了欧拉路对点度数的需求。
想让这张图连通,需要把现有的已经连通的部分缩成一个点,然后在上面求最小生成树。易得让图连通需要的最小代价就是最小生成树长度和的两倍。
具体实现时,我们先处理所有管道,包括它们形成的连通块和需要的自由路径,然后枚举每个终点单独处理。求最小生成树的时候只需要加入所有必经的节点,而因为这张图中两点的距离就是数轴上距离,因此只需要加入相邻的必经点构成的边就一定能求出最小生成树。
时间复杂度(来自并查集和求 mst 时给边排序)。代码太丑了,就不放了。